﻿#include <iostream>
#include <unordered_map>
#include "BinaryTree.h"

using namespace std;

typedef struct  
{
	int left;
	int right;
	int me;
}TopologicalStructureData;

static void maxSizeOfTopologicalStructure(BinaryTreeNode* head, unordered_map<BinaryTreeNode*, TopologicalStructureData>& topoMap)
{	
	if (!head) return;

	TopologicalStructureData data;
	memset(&data, 0, sizeof(TopologicalStructureData));

	data.me = 1;
	maxSizeOfTopologicalStructure(head->left, topoMap);
	maxSizeOfTopologicalStructure(head->right, topoMap);

	// 遍历左子树的右边界
	BinaryTreeNode* rightEdgeNode = head->left;
	TopologicalStructureData edgeData;
	while (rightEdgeNode && rightEdgeNode->getValue() < head->getValue())
	{
		edgeData = topoMap[rightEdgeNode];
		data.left += edgeData.left + edgeData.me;
		rightEdgeNode = rightEdgeNode->right;
	}

	// 遍历右子树的左边界
	BinaryTreeNode* leftEdgeNode = head->right;
	while (leftEdgeNode && leftEdgeNode->getValue() > head->getValue())
	{
		edgeData = topoMap[leftEdgeNode];
		data.right += edgeData.right + edgeData.me;
		leftEdgeNode = leftEdgeNode->left;
	}

	topoMap[head] = data;
}

#define MAX(a,b) (a>b?a:b)

/**
 * 给定一颗二叉树的头结点head，已知所有节点的值都不一样，返回其中最大的且符合搜索二叉树条件的最大拓扑结构的大小。
 * 拓扑结构: 不是子树，只要能连起来的结构都算。
 * 
 * 思路：
 * 先普及一个概念: 拓扑贡献记录
 * 
 * 有一颗二叉树：
 *                    5
 *                  /   \
 *                 3     10
 *               /  \   /   \
 *              6    4 3    12
 * 
 * 以5作为头部的满足搜索二叉树条件的拓扑结构，如下：
 * 
 *                    5
 *                  /   \
 *                 3     10
 *                  \      \
 *                   4     12
 * 
 * 6和3由于不符合搜索二叉树的条件，故需要去掉。
 * 6的左子树为5贡献的节点数量是0,6的右子树为5贡献的节点数量是0；
   4的左子树为5贡献的节点数量是0,4的右子树为5贡献的节点数量是0；
   3的左子树为5贡献的节点数量是0,3的右子树为5贡献的节点数量是1(包含:4)；
   5的左子树为5贡献的节点数量是2(包含:3,4)。
   12的左子树为5贡献的节点数量是0,12的右子树为5贡献的节点数量是0；
   10的左子树为5贡献的节点数量是0,10的右子树为5贡献的节点数量是1(包含:12)；
   5的左子树为5贡献的节点数量是2(包含:10,12)。

   故以5作为头部的拓扑贡献记录可以表示如下:

 *                    5
 *         (2) /               \ (2)
 *            3                 10
 *     (0)/       \(1)   (0)/       \(1)
 *      6         4         3        12
 *  (0)/ \(0) (0)/ \(0) (0)/ \(0) (0)/ \(0)
 * 
 * 当来到某个节点X的时候，先生成X->left的拓扑贡献记录，再生成X->right的拓扑贡献记录，有了这些记录，就可以生成X的拓扑贡献记录了，只要沿着X->left的右边界，将不满足搜索树条件的节点去掉，再更新X->left的拓扑贡献记录；再沿着X->right的左边界，将不满足搜索树条件的节点去掉，再更新X->right的拓扑贡献记录。这样，X的拓扑贡献记录就得到了。
 * 用这个方法，将每个节点的拓扑贡献记录都得到，然后选取最大的即可。
 */
int main_maxSizeOfTopologicalStructure()
{
	BinaryTreeNode* head = new BinaryTreeNode(0, 5);
	head->left = new BinaryTreeNode(1, 3);
	head->right = new BinaryTreeNode(2, 10);
	head->left->left = new BinaryTreeNode(3, 6);
	head->left->right = new BinaryTreeNode(4, 4);
	head->right->left = new BinaryTreeNode(5, 6);
	head->right->left->left = new BinaryTreeNode(10, 1);
	head->right->left->right = new BinaryTreeNode(11, 8);
	head->right->left->right->left = new BinaryTreeNode(12, 7);
	head->right->left->right->right = new BinaryTreeNode(13, 9);

	head->right->right = new BinaryTreeNode(6, 12);

	unordered_map<BinaryTreeNode*, TopologicalStructureData> topoMap;
	maxSizeOfTopologicalStructure(head, topoMap);

	int maxSize = 0;
	int cur;
	for (auto it = topoMap.begin(); it != topoMap.end(); it++)
	{
		printf("key:(%d,%d) left:%d right:%d\n", 
			it->first->getId(), it->first->getValue(), it->second.left, it->second.right);
		cur = it->second.left + it->second.right + it->second.me;
		maxSize = MAX(maxSize, cur);
	}

	printf("%d\n", maxSize);

	return 0;
}